#include "big_int_t.h"

big_int_t::big_int_t() : shift_(0)
{
   digits_.push_back(0);
}

big_int_t::big_int_t(unsigned long long digit) : shift_(0)
{
   digits_.push_back(digit);
}

big_int_t::big_int_t(std::string str) : shift_(0)
{
   std::reverse(str.begin(), str.end());

   int counter = 0;
   digit_t tmp = 0;

   digits_.clear();

   int len = str.length();
   for (int i = 0; i < len; i++)
   {
      if (counter == big_int_t::DIGIT_LENGTH)
      {
         digits_.push_back(tmp);
         tmp = 0;
         counter = 0;
      }

      int d = (str[i] - '0');
      for (int i = 0; i < counter; i++)
      {
         d *= 10;
      }
      tmp += d;
      counter++;
   }

   digits_.push_back(tmp);
   
   if (digits_.size() == 0)
   {
      digits_.push_back(0);
   }
}

int big_int_t::compare_to(const big_int_t& bigint) const
{
   if (digits_.size() + shift_ != bigint.digits_.size() + bigint.shift_)
   {
      if (digits_.size() + shift_ < bigint.digits_.size() + bigint.shift_)
      {
         return -1;
      }
      else
      {
         return 1;
      }
   }
   int len = digits_.size();
   for (int i = len - 1; i >= 0; i--)
   {
      int j = i - bigint.shift_ + shift_;
      digit_t d = (0 <= j && j < static_cast<int>(bigint.digits_.size())) ? bigint.digits_[j] : 0;
      if (digits_[i] < d) {
         return -1;
      }
      if (digits_[i] > d) {
         return 1;
      }
   }
   return 0;
}

bool big_int_t::operator<(const big_int_t& bigint) const
{
   return compare_to(bigint) < 0;
}

bool big_int_t::operator>(const big_int_t& bigint) const
{
   return compare_to(bigint) > 0;
}

bool big_int_t::operator<=(const big_int_t& bigint) const
{
   return compare_to(bigint) <= 0;
}

bool big_int_t::operator>=(const big_int_t& bigint) const
{
   return compare_to(bigint) >= 0;
}

bool big_int_t::operator==(const big_int_t& bigint) const
{
   return compare_to(bigint) == 0;
}

bool big_int_t::operator!=(const big_int_t& bigint) const
{
   return compare_to(bigint) != 0;
}

big_int_t& big_int_t::operator+=(const big_int_t& bigint)
{   
   if (digits_.size() + shift_ < bigint.digits_.size() + bigint.shift_)
   {
      digits_.resize(bigint.digits_.size() + bigint.shift_ - shift_, 0);
   }

   if (shift_ > bigint.shift_)
   {
      digits_.insert(digits_.begin(), shift_ - bigint.shift_, 0);
      shift_ = bigint.shift_;
   }
   
   int len = bigint.digits_.size();
   for (int i = 0; i < len; i++)
   {
      unsigned int k = i - shift_ + bigint.shift_;
      digits_[k] += bigint.digits_[i];
   }

   normalize();

   return *this;
}

big_int_t& big_int_t::operator-=(const big_int_t& bigint)
{
   if (shift_ > bigint.shift_)
   {
      digits_.insert(digits_.begin(), shift_ - bigint.shift_, 0);
      shift_ = bigint.shift_;
   }
   
   int len = bigint.digits_.size();
   for (int i = 0; i < len; i++)
   {
      unsigned int k = i - shift_ + bigint.shift_;
      digits_[k] -= bigint.digits_[i];
   }

   normalize();

   cut_zeroes();

   return *this;
}

big_int_t& big_int_t::operator*=(digit_t digit)
{
   if (digit == 0)
   {
      *this = big_int_t(0);
      return *this;
   }
   
   int len = digits_.size();
   for (int i = 0; i < len; i++)
   {
      digits_[i] *= digit;
   }

   normalize();

   return *this;
}

big_int_t big_int_t::operator*(digit_t digit) const
{
   big_int_t tmp = *this;
   tmp *= digit;

   return tmp;
}

std::pair<big_int_t, big_int_t> big_int_t::divide_with_remainder(const big_int_t& bigint) const
{
   big_int_t a = *this;
   big_int_t b = bigint;
   big_int_t result;

   int shift = a.digits_.size() - b.digits_.size();
   b <<= shift;

   while (a >= bigint)
   {
      digit_t k = a.find_short_divider(b);
      result <<= 1;
      result += big_int_t(k);
      a -= b * k;
      b >>= 1;
      shift--;
   }

   if (shift + 1 > 0)
   {
      result <<= shift + 1;
   }
   result.cut_zeroes();

   return std::make_pair(result, a);
}

big_int_t& big_int_t::operator<<=(int shift)
{
   shift_ += shift;

   return *this;
}

big_int_t& big_int_t::operator>>=(int shift)
{
   shift_ -= shift;

   return *this;
}

big_int_t big_int_t::operator<<(int shift) const
{
   big_int_t tmp = *this;
   tmp <<= shift;

   return tmp;
}

big_int_t big_int_t::operator>>(int shift) const
{
   big_int_t tmp = *this;
   tmp >>= shift;

   return tmp;
}

std::istream& operator>>(std::istream &is, big_int_t &bigint)
{
   while (std::isspace(is.peek()))
   {
      is.get();
   }

   if (is.eof() || !isdigit(is.peek())) {
      is.setstate(std::ios_base::badbit);
      return is;
   }

   std::ostringstream ss;

   while (isdigit(is.peek()))
   {
      char tmp;
      is.get(tmp);
      ss << tmp;
   }
   
   bigint = big_int_t(ss.str());

   return is;
}

std::ostream& operator<<(std::ostream &os, const big_int_t &bigint)
{
   int size = bigint.digits_.size();
   for (int i = size - 1; i >= 0; i--)
   {
      std::ostringstream out;
      out << bigint.digits_[i];
      std::string str = out.str();

      if (i != size - 1)
      {
         int count = big_int_t::DIGIT_LENGTH - str.length();
         for (int i = 0; i < count; i++)
         {
            os << "0";
         }
      }

      os << str;
   }

   std::string zero(bigint.DIGIT_LENGTH, '0');
   for (int i = 0; i < bigint.shift_; i++)
   {
      os << zero;
   }

   return os;
}

void big_int_t::normalize()
{
   int size = digits_.size();
   for (int i = 0; i < size; i++)
   {
      if (digits_[i] > BASE)
      {
         if (i == size - 1)
         {
            digits_.push_back(digits_[i] / BASE);
         }
         else
         {
            digits_[i + 1] += digits_[i] / BASE;
         }
         digits_[i] %= BASE;
         continue;
      }
      if (digits_[i] < 0)
      {
         digit_t borrow = (-digits_[i]) / BASE;
         if ((-digits_[i]) % BASE != 0)
         {
            borrow++;
         }
         digits_[i] += BASE * borrow;
         if (i < size - 1)
         {
            digits_[i + 1] -= borrow;
         }
      }
   }
}

digit_t big_int_t::find_short_divider(const big_int_t& bigint) const
{
   digit_t l = 0;
   digit_t r = BASE;
   digit_t m = (l + r) / 2;
   while (l + 1 != r)
   {
      if (*this < bigint * m)
      {
         r = m;
      }
      else
      {
         l = m;
      }
      m = (l + r) / 2;
   }

   return m;
}

void big_int_t::cut_zeroes()
{
   while (digits_.size() > 1 && digits_[digits_.size() - 1] == 0)
   {
      digits_.pop_back();
   }
}